Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 11656 - Message in the Enemy Territory / 11656.cpp
blobcb3016828b46a1513d1401c1e5050f725868b47f
1 // Wrong Answer
2 // Just to make sure the input is well formed and there are no three
3 // consecutive collineal points in the border of the resulting polygon.
4 using namespace std;
5 #include <algorithm>
6 #include <iostream>
7 #include <iterator>
8 #include <numeric>
9 #include <sstream>
10 #include <fstream>
11 #include <cassert>
12 #include <climits>
13 #include <cstdlib>
14 #include <cstring>
15 #include <string>
16 #include <cstdio>
17 #include <vector>
18 #include <cmath>
19 #include <queue>
20 #include <deque>
21 #include <stack>
22 #include <list>
23 #include <map>
24 #include <set>
26 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
27 #define For(i, a, b) for (int i=(a); i<(b); ++i)
28 #define D(x) cout << #x " is " << x << endl
30 const int MAXC = 1035;
32 typedef pair< int, int > point;
33 typedef pair< point, point > side;
35 vector< int > YgivenX[MAXC], XgivenY[MAXC];
36 vector< side > sides;
38 bool isSimpleClosedPolygon() {
39 point start = sides[0].first;
41 set<point> seen;
42 point cur = start;
44 do {
45 seen.insert(cur);
46 point next;
48 printf("Inserted <%d, %d>\n", cur.first, cur.second);
49 for (int i = 0; i < sides.size(); ++i) {
50 if (sides[i].first == cur or sides[i].second == cur) {
51 next = sides[i].first == cur ? sides[i].second : sides[i].first;
52 assert(next != cur);
53 if (seen.count(next) == 0) {
54 break;
58 printf("next = <%d, %d>\n", next.first, next.second);
59 cur = next;
60 } while (cur != start);
62 return seen.size() == sides.size();
65 int main(){
66 int n, m;
67 while (cin >> n >> m) {
68 if (n == 0 and m == 0) break;
70 assert(n % 2 == 0);
72 For(i, 0, MAXC) YgivenX[i].clear(), XgivenY[i].clear();
74 For(i, 0, n) {
75 int x, y; cin >> x >> y;
76 XgivenY[y].push_back( x );
77 YgivenX[x].push_back( y );
79 int x1, y1, x2, y2;
80 cin >> x1 >> y1 >> x2 >> y2;
82 sides.clear();
84 For(x, 0, MAXC) {
85 sort(YgivenX[x].begin(), YgivenX[x].end());
86 assert(YgivenX[x].size() % 2 == 0);
87 for (int k = 0; k < YgivenX[x].size(); k += 2) {
88 int y = YgivenX[x][k];
89 int nextY = YgivenX[x][k+1];
91 sides.push_back( side(point(x, y), point(x, nextY)) );
95 For(y, 0, MAXC) {
96 sort(XgivenY[y].begin(), XgivenY[y].end());
97 assert(XgivenY[y].size() % 2 == 0);
98 for (int k = 0; k < XgivenY[y].size(); k += 2) {
99 int x = XgivenY[y][k];
100 int nextX = XgivenY[y][k+1];
102 sides.push_back( side(point(x, y), point(nextX, y)) );
106 assert(sides.size() == n);
107 for (int i = 0; i < sides.size(); ++i) {
108 printf("There's a side from <%d, %d> to <%d, %d>\n", sides[i].first.first, sides[i].first.second, sides[i].second.first, sides[i].second.second);
110 assert(isSimpleClosedPolygon());
111 puts("NO");
113 return 0;